package q1000_q1999;

/**
 * @Author: wzp
 * @CreateTime: 2024-09-23  13:50
 * @Description: 最佳观光组合
 * @Version: 1.0
 */








public class q_1014 {
    public int maxScoreSightseeingPair(int[] values) {
//        int max=Integer.MIN_VALUE;
//        int len=values.length;
//        for (int i = 0; i < values.length-1; i++) {
//            for (int j = i+1; j <values.length ; j++) {
//                int temp=values[i]+values[j]+i-j;
//                if(temp>max){
//                    max=temp;
//                }
//            }
//        }
//        return max;
//        采用动态规划的方法
        int len=values.length;
        int result=values[len-1]+values[len-2]-1;
        int[] dp=new int[len-1];
        dp[len-2]=result;
        for (int i = len-3; i >=0 ; i--) {
            int temp=values[i]+values[i+1]-1;
            int dp_value=values[i]-values[i-1]+dp[i-1]-1;
            dp[i]=temp>dp_value?temp:dp_value;
            if(dp[i]>result){
                result=dp[i];
            }
        }
        return result;
    }

}
